/*
 * @lc app=leetcode.cn id=16 lang=golang
 * @lcpr version=30118
 *
 * [16] 最接近的三数之和
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
import (
	"math"
	"sort"
)

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	closestSum := nums[0] + nums[1] + nums[2]
	for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		left, right := i+1, len(nums)-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == target {
				return target
			} else {
				if math.Abs(float64(sum-target)) < math.Abs(float64(closestSum-target)) {
					closestSum = sum
				}
				if sum < target {
					left++
				} else {
					right--
				}
			}
		}
	}
	return closestSum
}

// @lc code=end

/*
// @lcpr case=start
// [-1,2,1,-4]\n1\n
// @lcpr case=end

// @lcpr case=start
// [0,0,0]\n1\n
// @lcpr case=end

*/

